#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;           //数据域
    struct Node *pNext; //指针域
} NODE, *PNODE;         //NODE等价于struct Node    PNODE等价于struct Node *

//创建链表
PNODE create_list()
{
    int len; //用来存放有效节点的个数
    int val; //用来临时存放用户输入的结点的值

    //分配了一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("分配失败, 程序终止!\n");
        exit(-1);
    }

    // 定义一个临时结构体指针指向最后一个结点
    PNODE pTail = pHead;
    pTail->pNext = NULL;

    printf("请输入您需要生成的链表节点的个数: len = ");
    scanf("%d", &len);
    for (int i = 0; i < len; ++i)
    {
        printf("请输入第%d个节点的值: ", i + 1);
        scanf("%d", &val);
        //新结点
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew)
        {
            printf("分配失败, 程序终止!\n");
            exit(-1);
        }
        pNew->data = val;
        pNew->pNext = NULL;
        // 将之前的最后一个结点指向新结点
        pTail->pNext = pNew;
        //再将pTail指向新的最后一个结点
        pTail = pNew;
    }
    return pHead;
}

//头插法创建链表(每一个新结点插入到上一个结点的前面)
PNODE create_list_head()
{
    int len; //用来存放有效节点的个数
    int val; //用来临时存放用户输入的结点的值

    //分配了一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("分配失败, 程序终止!\n");
        exit(-1);
    }
    pHead->pNext = NULL;
    printf("请输入您需要生成的链表节点的个数: len = ");
    scanf("%d", &len);
    for (int i = len; i > 0; i--)
    {
        //新结点
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew)
        {
            printf("分配失败, 程序终止!\n");
            exit(-1);
        }
        printf("请输入第%d个节点的值: ", i);
        scanf("%d", &val);
        pNew->data = val;
        //pHead->pNext就是上一个结点的地址
        pNew->pNext = pHead->pNext;
        pHead->pNext = pNew;
    }
    return pHead;
}

//遍历链表
void traverse_list(PNODE pHead)
{
    //获取第一个结点的地址
    PNODE p = pHead->pNext;
    while (p != NULL)
    {
        printf("%d  ", p->data);
        //将结点的指针域(下一个结点的地址)赋值给p
        p = p->pNext;
    }
    printf("\n");
}

//判断链表是否为空
bool is_empty(PNODE pHead)
{
    if (pHead->pNext == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//求链表长度
int length_list(PNODE pHead)
{

    PNODE p = pHead->pNext;
    int len = 0;
    while (p != NULL)
    {
        len++;
        p = p->pNext;
    }
    return len;
}

//排序
void sort_list(PNODE pHead)
{
    int i, j, t;
    int len = length_list(pHead);
    int arr[] = {5, 10, 1, 4, 2};
    PNODE q, p;
    for (i = 0, q = pHead->pNext; i < len - 1; i++, q = q->pNext)
    {
        for (j = i + 1, p = q->pNext; j < len; j++, p = p->pNext)
        {

            if (q->data > p->data) //arr[i] > arr[j]
            {
                t = q->data;       //t = arr[i];
                q->data = p->data; //arr[i] = arr[j];
                p->data = t;       //arr[j] = t;
            }
        }
    }
    return;
}

//在pHead所指向链表的第pos个节点的前面插入一个新的结点，
// 该节点的值是val， 并且pos的值是从1开始
bool insert_list(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;

    while (NULL != p && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos - 1 || NULL == p) //大于表长或者小于1都不可以
        return false;

    //分配了一个不存放有效数据的头结点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("分配失败, 程序终止!\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->pNext = p->pNext;
    p->pNext = pNew;
    //不可倒序
    printf("插入结果");
    return true;
}

//***为什么插入是循环是p，删除是p->pNext？
//***因为插入i可以加到最后的元素位置，删除的i必须在倒数第二停住

//删除
bool delete_list(PNODE pHead, int pos)
{
    int i = 0;
    PNODE p = pHead;

    while (NULL != p->pNext && i < pos - 1)
    {
        ++i;
        p = p->pNext;
    }

    if (i > pos - 1 || NULL == p->pNext)
        return false;

    //如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    PNODE q = p->pNext;
    p->pNext = p->pNext->pNext;
    //释放q所指向的节点所占的内存
    free(q);
    //变量的值清空
    q = NULL;
    printf("删除结果\n");
    return true;
}

//取第i个元素的值
int getElem(PNODE pHead, int i)
{
    int j = 1; //定义一个计数器
    PNODE p;
    p = pHead->pNext;
    //p不为空且j还有等于i的时候(如果就是第一个元素那么直接调过循环)
    while (p && j < i)
    {
        j++;
        p = p->pNext;
    }

    if (p == NULL || j > i)
    {
        return -1;
    }

    return p->data;
}

//按值查找,并返回所在的位置
int locate(PNODE pHead, int e)
{
    int i = 1;
    PNODE p = pHead->pNext;
    while (p && p->data != e)
    {
        i++;
        p = p->pNext;
    }
    if (p)
    {
        return i;
    }
    else
    {
        return -1;
    }
}

//销毁(包括头结点)
void destoryList(PNODE pHead)
{
    PNODE p;
    while (pHead)
    {
        //先移动头指针的指向，再去用释放p所对应的空间
        p = pHead;
        pHead = pHead->pNext;
        free(p);
        p = NULL;
    }
}

//清空
// 链表仍然存在将其置空(头结点和头指针仍然存在)
void cleanList(PNODE pHead)
{
    PNODE p, q; //p用来存储上一个结点，q用来移动指针
    //先移动在释放
    p = pHead->pNext;
    while (p)
    {
        q = p->pNext;
        free(p);
        p = NULL;
        p = q;
    }
    //pHead的指针域要清空
    pHead->pNext = NULL;
}

int main(void)
{
    PNODE pHead = NULL;
    //create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHead
    pHead = create_list_head();
    //循环遍历
    traverse_list(pHead);
    //判断是否为空
    if (is_empty(pHead))
        printf("链表为空!\n");
    else
        printf("链表不空!\n");
    //链接长度
    int len = length_list(pHead);
    printf("链表的长度是%d\n", len);
    //链表排序
    sort_list(pHead);
    //循环遍历
    traverse_list(pHead);
    //插入
    // insert_list(pHead, 2, 33);
    //删除
    delete_list(pHead, 3);
    //循环遍历
    traverse_list(pHead);

    return 0;
}